//041. 最大的 n 位 pandigital 质数
//        如果一个数字将 1 到 n 的每个数字都使用且只使用了一次，我们将其称其为一个 n 位的
//        pandigital 数（也称为全数字）。例如，2143 是一个 4 位的 pandigital 数，并且是一个质数。
//        求最大的 n 位 pandigital 质数是多少？
//        答案：7652413


public class Week041 {
    //余6法
    //当x%6=±1时，x可能是质数，否则一定不是质数
    public static boolean isPrime(int n) {
        if (n <= 3) return n > 1;
        if (n % 6 != 1 && n % 6 != 5) return false;
        for (int i = 5, sq = (int) Math.sqrt(n); i <= sq; i += 6)
            if (n % i == 0 || n % (i + 2) == 0) return false;
        return true;
    }

    static int ans = 2143;
    static int[] nums = new int[9];
    static boolean[] book = new boolean[9];
    static int n;

    static void dfs(int len) {
        if (len == n) {
            int cur = nums[0];
            for (int i = 1; i < len; ++i) {
                cur = cur * 10 + nums[i];
            }
            if (cur > ans && isPrime(cur)) ans = cur;
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (book[i]) continue;
            nums[len] = i + 1;
            book[i] = true;
            dfs(len + 1);
            book[i] = false;
        }
    }

    static void run() {
        for (n = 4; n <= 9; ++n) {
            dfs(0);
        }
        System.out.println(ans);
    }

    public static void main(String[] args) {
        long startTime = System.nanoTime();
        run();
        System.out.println("\n程序运行时间：" + (System.nanoTime() - startTime) + "ns.");
    }
}
